package com.zy.graph;

import java.util.*;

/**
 * @author zhaoyi
 * @date 2021/12/22 2:01 下午
 */
public class SolutionIslands {


    //思想同numIslands一样 效率更高
    public int numIslands2(char[][] grid) {
        int count = 0;
        if (grid == null || grid.length == 0)
            return count;

        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                //只有当前格子是1才开始计算
                if (grid[i][j] == '1') {
                    //如果当前格子是1，岛屿的数量加1
                    count++;
                    //然后通过bfs把当前格子的上下左右4
                    //个位置为1的都要置为0，因为他们是连着
                    //一起的算一个岛屿，
                    bfs2(grid, i, j);
                }
            }
        return count;

    }

    private void bfs2(char[][] grid, int x, int y) {
        //把当前格子先置为0
        grid[x][y] = '0';
        int n = grid.length;
        int m = grid[0].length;
        //使用队列，存储的是格子坐标转化的值
        Queue<Integer> queue = new LinkedList<>();
        //我们知道平面坐标是两位数字，但队列中存储的是一位数字，
        //所以这里是把两位数字转化为一位数字
        int code = x * m + y;
        //坐标转化的值存放到队列中
        queue.add(code);
        while (!queue.isEmpty()) {
            //出队
            code = queue.poll();
            //在反转成坐标值（i，j）
            int i = code / m;
            int j = code % m;
            if (i > 0 && grid[i - 1][j] == '1') {//上
                //如果上边格子为1，把它置为0，然后加入到队列中
                //下面同理
                grid[i - 1][j] = '0';
                queue.add((i - 1) * m + j);
            }
            if (i < n - 1 && grid[i + 1][j] == '1') {//下
                grid[i + 1][j] = '0';
                queue.add((i + 1) * m + j);
            }
            if (j > 0 && grid[i][j - 1] == '1') { //左
                grid[i][j - 1] = '0';
                queue.add(i * m + j - 1);
            }
            if (j < m - 1 && grid[i][j + 1] == '1') {//右
                grid[i][j + 1] = '0';
                queue.add(i * m + j + 1);
            }
        }
    }


    //效率差很多
    public int numIslands(char[][] grid) {
        //需要访问的点
        Map<Vs, Boolean> visited = new HashMap<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                char c = grid[i][j];
                if (c == '1') {
                    Vs vs = new Vs(i, j);
                    visited.put(vs, false);
                }
            }
        }

        int count = 0;
        if (visited.isEmpty()) {
            return count;
        }
        Queue<Vs> queue = new LinkedList<>();

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                Vs key = new Vs(i, j);
                Boolean aBoolean = visited.get(key);
                if (aBoolean != null && !aBoolean) {
                    queue.add(key);
                    visited.put(key, true);
                    count++;
                    while (!queue.isEmpty()) {
                        Vs poll = queue.poll();
                        //左边
                        int left = poll.j - 1;
                        if (left >= 0) {
                            char c = grid[poll.i][left];
                            Vs vs = new Vs(poll.i, left);
                            if (c == '1' && !visited.get(vs)) {
                                queue.add(vs);
                                visited.put(vs, true);
                            }
                        }

                        //右边
                        int right = poll.j + 1;
                        if (right < grid[0].length) {
                            char c = grid[poll.i][right];
                            Vs vs = new Vs(poll.i, right);
                            if (c == '1' && !visited.get(vs)) {
                                queue.add(vs);
                                visited.put(vs, true);
                            }
                        }


                        //上面
                        int up = poll.i - 1;
                        if (up >= 0) {
                            Vs vs = new Vs(up, poll.j);
                            char c = grid[up][poll.j];
                            if (c == '1' && !visited.get(vs)) {
                                queue.add(vs);
                                visited.put(vs, true);
                            }
                        }

                        //下面
                        int down = poll.i + 1;
                        if (down < grid.length) {
                            Vs vs = new Vs(down, poll.j);
                            char c = grid[down][poll.j];
                            if (c == '1' && !visited.get(vs)) {
                                queue.add(vs);
                                visited.put(vs, true);
                            }
                        }
                    }
                }

            }
        }

        return count;

    }

    class Vs {
        int i;
        int j;

        public Vs(int i, int j) {
            this.i = i;
            this.j = j;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vs vs = (Vs) o;
            return i == vs.i && j == vs.j;
        }

        @Override
        public int hashCode() {
            return Objects.hash(i, j);
        }

        @Override
        public String toString() {
            return "Vs{" +
                    "i=" + i +
                    ", j=" + j +
                    '}';
        }
    }

}
